package com.javabasic.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/6/22 22:08
 */
public class FindBottomLeftTreeValue {


    private int maxHeight = -1;
    private int result;
    private boolean finish;

    /**
     * 暴力解法
     * 1. 计算高度
     * 2. 获取最底层从左到右的第一个数
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {

        getHeight(root, 0);
        maxHeight--;

        System.out.println(maxHeight);

        finish = false;
        getResult(root, 0);

        return result;

    }

    private void getResult(TreeNode root, int len) {
        if (root == null) {
            return;
        }
        if (finish) {
            return;
        }
        if (len == maxHeight) {
            result = root.val;
            finish = true;
            return;
        }
        getResult(root.left, len + 1);
        getResult(root.right, len + 1);
    }

    private void getHeight(TreeNode root, int len) {
        if (root == null) {
            if (len > maxHeight) {
                maxHeight = len;
            }
            return;
        }

        getHeight(root.left, len + 1);
        getHeight(root.right, len + 1);
    }


    /**
     * 解法二: 中序遍历的时候同时记录下最底层从左到右的第一个数
     * @param root
     * @return
     */
    public int findBottomLeftValue2(TreeNode root) {

        inorderTraversal(root, 0);

        return result;

    }

    private void inorderTraversal(TreeNode root, int len) {
        if (len > maxHeight && root != null) {
            maxHeight = len;
            result = root.val;
        }
        if (root.left != null) {
            inorderTraversal(root.left, len+1);
        }
        if (root.right != null) {
            inorderTraversal(root.right, len+1);
        }
    }

    /**
     * 解法三： 层序遍历 + 从右往左遍历
     * @param root
     * @return
     */
    public int findBottomLeftValueMethodOfTwo(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            if (root.right != null) queue.offer(root.right);
            if (root.left != null) queue.offer(root.left);
        }
        return root.val;
    }
}
